﻿//class Solution
//{
//	int n, m;
//	int x1, y1, x2, y2;
//	int dist[15][15] = { 0 };
//	int cnt[15][15] = { 0 };
//	int dx[4] = { 0, 0, 1, -1 };
//	int dy[4] = { 1, -1, 0, 0 };
//
//	int bfs(vector<vector<int> >& CityMap)
//	{
//		memset(dist, -1, sizeof dist);
//		queue<pair<int, int>> q;
//		q.push({ x1, y1 });
//		dist[x1][y1] = 0;
//		cnt[x1][y1] = 1;
//		while (q.size())
//		{
//			auto [a, b] = q.front();
//			q.pop();
//			for (int i = 0; i < 4; i++)
//			{
//				int x = a + dx[i], y = b + dy[i];
//				if (x >= 0 && x < n && y >= 0 && y < m && CityMap[x][y] != -1)
//				{
//					if (dist[x][y] == -1) // 第⼀次到这个位置
//					{
//						dist[x][y] = dist[a][b] + 1;
//						cnt[x][y] += cnt[a][b];
//						q.push({ x, y });
//					}
//					else // 不是第⼀次到这个位置
//					{
//						if (dist[a][b] + 1 == dist[x][y]) // 是不是最短路
//						{
//							cnt[x][y] += cnt[a][b];
//						}
//					}
//				}
//			}
//		}
//		return cnt[x2][y2];
//	}
//public:
//	int countPath(vector<vector<int> >& CityMap, int _n, int _m)
//	{
//		n = _n, m = _m;
//		for (int i = 0; i < n; i++)
//		{
//			for (int j = 0; j < m; j++)
//			{
//				if (CityMap[i][j] == 1)
//				{
//					x1 = i, y1 = j;
//				}
//				else if (CityMap[i][j] == 2)
//				{
//					x2 = i, y2 = j;
//				}
//			}
//		}
//		return bfs(CityMap);
//	}
//};




//#include <iostream>
//#include <algorithm>
//using namespace std;
//const int N = 2e5 + 10;
//int n, x;
//int arr[N];
//int main()
//{
//	cin >> n >> x;
//	for (int i = 1; i <= n; i++) cin >> arr[i];
//
//	sort(arr + 1, arr + 1 + n);
//	long long ret = 0;
//	int index = max(0, n - x); 
//	ret += arr[index] * x;
//	for (int i = index + 1; i <= n; i++) ret += arr[i] - arr[index];
//
//	cout << ret << endl;
//
//	return 0;
//}


class Solution
{
	int arr[110] = { 0 };
	int dp[110][110] = { 0 };
public:
	int getCoins(vector<int>& coins)
	{
		int n = coins.size();
		arr[0] = arr[n + 1] = 1;
		for (int i = 1; i <= n; i++) arr[i] = coins[i - 1];
		for (int i = n; i >= 1; i--)
		{
			for (int j = i; j <= n; j++)
			{
				for (int k = i; k <= j; k++)
				{
					dp[i][j] = max(dp[i][j], dp[i][k - 1] + dp[k + 1][j] +
						arr[i - 1] * arr[k] * arr[j + 1]);
				}
			}
		}
		return dp[1][n];
	}
};